1. Field of the Invention
This invention relates to means for providing optimum plans when making diversified plans in various fields and in particular to means for solving planning problems involving an enormous number of permutations or combinations in a simple configuration and at an extremely high speed.
2. Description of the Related Art
Hitherto, various techniques have been proposed to find out, within a practical allowable time, an optimum solution or a plan for maximizing or minimizing a maximum or minimum item determined in planning problems intended for various problems in diversified fields, such as print pattern design of electronic wiring boards, manufacturing processes, sewage piping design, or physical distribution systems.
The techniques attempt to implement means for finding optimum solutions to the planning problems in various fields within the practical allowable time by applying an interconnecting neural network, chaos, etc., for example, as described in the references "Epoch-making Method for "Traveling Salesman Problem--Miraculously High Results Using Chaos," Kagaku Asahi, Feb.--1993 or in Japanese Patent Laid-Open No. Hei 2-304587 "System for Calculating Shortest Distance, Shortest Time, or Lowest Transportation Cost."
Attention is also given to a so-called genetic algorithm, as potential means for simulating the evolution of living things and finding on overall quasi-optimum resolution, as described in the document "HANDBOOK OF GENETIC ALGORITHM (Van Nostrand Reinhold Computer Library.)
In contrast to a so-called enumeration method in which all possible plan combinations are considered for a given planning problem, a common concept in recent optimization means containing application examples of interconnecting neural networks, chaos, etc., as mentioned above, is as follows: First, one plan is made and the contents of the plan are efficiently changed little by little (namely, an attempt is made to find an optimum solution in as few planning attempts as possible, without planning at random). The value of an objective function, a function representing the item to be finally maximized or minimized in the planning problem is evaluated and a plan, for example, a plan for reducing the objective function value, is finally adopted as a better candidate plan for finding an optimum solution, namely, a plan for maximizing or minimizing the objective function in a short time.
However, the conventional methods using neural networks, chaos, etc., have the following two problems; First, each time a new plan is made, predetermined processing for planning must be performed as many times as the result of raising the number of components of the plan, or planning parameters for optimizing the objective function, n, to at least between the second power and the third power (n.sup.2 to n.sup.3 times). Second, optimality is evaluated experimentally without the theoretical foundation of it being possible to arrive at an optimum solution and therefore it takes a long processing time to arrive at an optimum solution or a quasi-optimum solution. Therefore, the probability of arriving at an optimum solution is extremely low.
For example, in a system described in the above-mentioned document, it takes a long time (20 seconds) to solve the so-called travelling salesman problem (TSP) in which the shortest one of all possible routes on which a salesman visits 30 places only once each is determined even if a recent computer, such as a workstation having a capability of 10-100 MIPS, is used; moreover, it has a 3% chance of finding an erroneous optimum solution.
In contrast, the above-mentioned genetic algorithm relates the plan elements to "chromosomes," the main element of a gene in the evolution of living things, and provides a plurality of chromosomes in order to carry out a search for a global optimum solution.
Thus, although it is inferior to the means using neural networks, chaos, etc., in performance with respect to reliably finding an optimum solution, there is a high chance that the processing capability, particularly convergence on an optimum solution at the initial stage of retrieval, will be greatly improved. However, to simulate heredity and evolution, enormous processing of complicated crossover, mutation, evaluation, selection, re-evaluation, etc., must be repeated; it is extremely difficult to effectively apply the genetic algorithm to actual industrial fields.